Skip to main content

Construct Binary Tree from Preorder and Inorder Traversal

Question​

Given two arrays representing the preorder and inorder traversal of a binary tree, construct the binary tree.

Example 1
Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

Output: 
              3
            /   \
           9     20
              /   \
             15    7

Solution​

all//Construct Binary Tree from Preorder and Inorder Traversal.py


# Definition for a binary tree node
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def buildTree(self, preorder, inorder):
        if inorder:
            # Find the index of the root node in the inorder list
            idx = inorder.index(preorder.pop(0))
            # Create the root node
            root = TreeNode(inorder[idx])
            # Recursively build the left and right subtrees
            root.left = self.buildTree(preorder, inorder[0:idx])
            root.right = self.buildTree(preorder, inorder[idx+1:])
            return root